# PROBLEM STATEMENT:
# ==================
# You receive a credit C at a local store and would like to buy two items. You
# first walk through the store and create a list L of all available items. From
# this list you would like to buy two items that add up to the entire value of
# the credit. The solution you provide will consist of the two integers
# indicating the positions of the items in your list (smaller number first).
# For instance, with C=100 and L={5,75,25} the solution is 2,3; with C=200 and
# L={150,24,79,50,88,345,3} the solution is 1,4; and with C=8 and
# L={2,1,9,4,4,56,90,3} the solution is 4,5.
#
# SOLUTIONS:
# ==========
# There are two solutions here: naive and better. The naive solution simply try
# all combinations of numbers in the list and check if any makes up the target
# number. The better solution relies on the fact that substracting the right
# number from the target number will yield the other number in the list. So it
# employes a dictionary to *remember* other number's position. Building the
# dictionary should take O(n) and going through the list to do the subtracting
# will take another O(n). So the better algorithm still takes O(n) overall.

# this version has O(n^2) complexity
def naive_store_credit(C, L):
   length = len(L)
   for i in range(length):
      v = L[i]
      for j in range(length):
         if j != i:
            if v + L[j] == C:
               return i,j
               
# this version has O(n) complexity
def better_store_credit(C, L):
   table = { L[i]:i for i in range(len(L)) }
   for i in range(len(L)):
      j = table.get(C - L[i])
      if j != None:
         return min(i,j), max(i,j)

assert naive_store_credit(100, [5, 75, 25]) == better_store_credit(100, [5, 75, 25])
assert naive_store_credit(200, [150, 24, 79, 50, 88, 345, 3]) == better_store_credit(200, [150, 24, 79, 50, 88, 345, 3])
assert naive_store_credit(8, [2, 1, 9, 4, 4, 56, 90, 3]) == better_store_credit(8, [2, 1, 9, 4, 4, 56, 90, 3])

